class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1)+len(s2)!=len(s3):
            return False
        dp = [[False for _ in range(len(s3)+1)] for _ in range(len(s1)+1)]

        dp[0][0] = True
        for i in range(1, min(len(s3), len(s1))+1):
            if s3[i-1]==s1[i-1]:
                dp[i][i]=True
            else:
                break
        for i in range(1, min(len(s3), len(s2))+1):
            if s3[i-1]==s2[i-1]:
                dp[0][i]=True
            else:
                break

        for i1 in range(1, len(s1)+1):
            for i3 in range(i1+1, len(s3)+1):
                i2 = i3-i1
                if i2>len(s2):
                    break
                if dp[i1-1][i3-1] and s1[i1-1]==s3[i3-1]:
                    dp[i1][i3]=True
                if dp[i1][i3-1] and s2[i2-1]==s3[i3-1]:
                    dp[i1][i3]=True
        
        return dp[-1][-1]


print(Solution().isInterleave("a", "b", "a"))